package com.lry.basic.algorithm.tree;

public class S2 {


    public static void main(String[] args) {
        new S2().bstFromPreorder(new int[]{8,5,1,7,10,12});
    }

     public TreeNode bstFromPreorder(int[] preorder) {
            if(null==preorder||preorder.length<=0){
                return null;
            }
            return bstFromPreorder(preorder,0,preorder.length-1);
        }

        public TreeNode bstFromPreorder(int[] preorder,int start,int end) {
            if(start>end){
                return null;
            }
            if(start==end){
                return new TreeNode(preorder[start]);
            }
            TreeNode root = new TreeNode(preorder[start]);

            int leftEnd = -1;
            for(int i = start+1;i<=end;i++){
                if(preorder[i]>preorder[start]){
                    break;
                }
                leftEnd= i;
            }
            if(-1!=leftEnd){
                root.left = bstFromPreorder(preorder,start+1,leftEnd);
                root.right = bstFromPreorder(preorder,leftEnd+1,end);
            }else{
                root.right = bstFromPreorder(preorder,start+1,end);
            }


            return root;
        }


       class TreeNode {
           int val;
           TreeNode left;
           TreeNode right;

           public TreeNode(int val) {
               this.val = val;
           }
       }

}
